
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h> // for longjmp, setjmp etc..
#include <signal.h> // for signal handlers
#include <unistd.h> // for ualarm
#include <assert.h>
#include <string.h>
#include <sched.h>
#include "user_threads.h"
#include "common.h"

/* debugging macros */
#if 0
#define PRK(...) write(__VA_ARGS__)
#else
#define PRK(...)  {}
#endif

#ifndef JB_SP
#define JB_SP 4
#endif

/* local use defines */
#define UTHREAD_ZOMBIE_JOINED 3
#define UTHREAD_DELETED 4

/* Global variables */
uthread current;
uthread all_threads[UTHREAD_MAX_THREADS]; //NOAM: array of pointers to uthread
uthread_id next_open;

/* Declerations of header functions within the code */
void uthread_exit(int retval);

/* Decrlerations of static functions within the code */
static void reset_alarm();

static void sig_handler(int signum);
static int context_switch(uthread prev, uthread next);
void do_exit(uthread thread, int retval);
static int get_new_id();
static uthread get_next_running(uthread prev);
static void garbage_collector();
void deactivate_thread(uthread thread);

void find_next_and_cs(uthread thread);
void kill_all();

/* uthread init
 * starts using user threads. starts a clock (ualarm) for context switching
 * return:
 * UTHREAD_SUCCESS if initialization was success
 * UTHREAD_FAIL any fail (memory)
 */
int uthread_init() {
	uthread head = malloc(sizeof(*head));
	if (!head) {
		return UTHREAD_FAIL;
	}
	memset(all_threads,0,sizeof(all_threads));
	/* init global queues */
	head->id = 0;
	head->magic = 123456;
	head->magic2 = 7890;
	head->join_by = -1;
	head->join_to = -1;
	head->state = UTHREAD_RUNNING;
	head->prio = UTHREAD_MIN_PRIO;
	head->ret_value = UTHREAD_INVALID;
	head->args = NULL;
	head->func = NULL;
	head->ret_value_joined = NULL;
	if (uthread_mutex_init_general() != MUTEX_SUCCESS) {
		free(head);
		all_threads[0] = NULL;
		return UTHREAD_FAIL;
	}
	head->locked_mutexes = thread_list_create();
	if (!head->locked_mutexes) {
		free(head);
		all_threads[0]=NULL;
		return UTHREAD_FAIL;
	}
	head->mutex_waiting_on = NULL;
	current = head;
	all_threads[0] = current;
	activate_thread(head);
	atexit(&kill_all);
	signal(SIGALRM,sig_handler); /* NOAM: moved the signal cmd after i finish init */
	ualarm(UTHREAD_TIME_SLICE * current->prio,0);
	return UTHREAD_SUCCESS;
}

/* returns self ID of the current running uthread */
uthread_id uthread_self() {
	return current->id;
}

/* uthread_create(start_routing, arg, prio)
 * creates a new user thread and adds it to the running queue
 * input:
 * start_routine - a method to call when the thread first starts
 * arg - argument to give to the method start_routing
 * prio - an integer determines the size of the timeslice given to the thread
 *
 * output:
 * uthread_id of the created thread if successfull
 * UTHREAD_FAIL if create failed
 */
uthread_id uthread_create(UTHREAD_START_ROUTINE start_routine, void* arg,
                          int prio) {
	uthread_id new_id;
	uthread new_thread;
	lock_alarm();
	garbage_collector();
	new_id = get_new_id();
	new_thread = malloc(sizeof(*new_thread));
	if (new_id == UTHREAD_FAIL ||
						prio < UTHREAD_MIN_PRIO || prio > UTHREAD_MAX_PRIO) {
		new_id = UTHREAD_FAIL;
		goto out;
	}
	if (!new_thread) {
		new_id = UTHREAD_FAIL;
		goto out_unlock;
	}
	all_threads[new_id] = new_thread;
	new_thread->id = new_id;
	new_thread->prio = prio;
	new_thread->join_by = -1;
	new_thread->join_to = -1;
	new_thread->ret_value = UTHREAD_INVALID;
	new_thread->magic = 123456;
	new_thread->magic2 = 7890;
	new_thread->args = arg;
	new_thread->func = start_routine;
	new_thread->ret_value_joined = NULL;
	new_thread->stack = malloc(UTHREAD_DEF_STACK_SIZE);
	if (!new_thread->stack) {
		free(new_thread);
		all_threads[new_id] = NULL;
		new_id = UTHREAD_FAIL;
		goto out_unlock;
	}
	new_thread->locked_mutexes = thread_list_create();
	if (!new_thread->locked_mutexes) {
		free(new_thread);
		free(new_thread->stack);
		all_threads[new_id] = NULL;
		new_id = UTHREAD_FAIL;
		goto out_unlock;
	}
	new_thread->mutex_waiting_on = NULL;
	char c[200];
	int ret;
	activate_thread(new_thread);

	if (sigsetjmp(new_thread->current_instruction,1)) {
		/* welcome back! I missed you XOXO */
		reset_alarm();
		uthread_exit((current->func)(current->args));
	}
	/* first time of the set jump */
	new_thread->current_instruction->__jmpbuf[JB_BP] = ((long int)(new_thread->stack)) + UTHREAD_DEF_STACK_SIZE - 4;
	new_thread->current_instruction->__jmpbuf[JB_SP] = ((long int)(new_thread->stack)) + UTHREAD_DEF_STACK_SIZE - 16;	
out_unlock:
	unlock_alarm();
out:
	return new_id;
}

/* uthread_exit(retval)
 * the current thread canceled itself
 * input:
 * retval - the return value the thread wishes to return
 *
 * output:
 * nothing as this thread no longer exists after the call of the method
 */
 
void uthread_exit(int retval) {
	lock_alarm();
	do_exit(current, retval);
	find_next_and_cs(current);
}

/* uthread_cancel(th)
 * cancels a given thread via its ID
 * input:
 * th - the ID of the thread the current thread wishes to kill
 *
 * output:
 * UTHREAD_INVALID - thread "th" does not exist
 * UTHREAD_FAIL - any other error
 * UTHREAD_SUCCESS - kill was successfull
 */
int uthread_cancel(uthread_id th) {
	lock_alarm();
	if (!all_threads[th] || all_threads[th]->state == UTHREAD_DELETED) {
		unlock_alarm();
		return UTHREAD_INVALID;
	}
	else if (!(all_threads[th]->state==UTHREAD_RUNNING || all_threads[th]->state==UTHREAD_SUSPENDED)) {
		unlock_alarm();
		return UTHREAD_FAIL;
	}
	do_exit(all_threads[th],UTHREAD_CANCELLED);
	if (current->id == th) {
		find_next_and_cs(current);
	}
	unlock_alarm();
	return UTHREAD_SUCCESS;
}

/* uthread_join(th, thread_return)
 * Suspends the current thread until thread "th" finishes.
 * saves (if a non-null pointer given) the return value of the thread
 * input:
 * th - thread id the current thread joins to
 * thread_return - pointer to which th thread stores the return value
 * 
 * output:
 * UTHREAD_INVALID: thread th does not exist
 * UTHREAD_FAIL: any other fail
 * UTHREAD_SUCCESS: thread joined successfully
 */
int uthread_join(uthread_id th, int* thread_return) {
	int retval;
	COND_ASSERT(current->join_to < 0); /* if it's >=0, then thread should be asleep */
	lock_alarm();
	if (th < 0 || th > UTHREAD_MAX_THREADS || !all_threads[th] ||
			all_threads[th]->state == UTHREAD_DELETED) {
		retval = UTHREAD_INVALID;
		thread_return = NULL;
		goto out_unlock;
	}
	if (current->id == th ||
		all_threads[th]->join_by > -1 ||
		all_threads[th]->state == UTHREAD_ZOMBIE_JOINED) {
		/* Trying to join an already joined */
		retval = UTHREAD_FAIL;
		thread_return = NULL;
		goto out_unlock;
	}

	if (all_threads[th]->state == UTHREAD_ZOMBIE) {
		all_threads[th]->state = UTHREAD_ZOMBIE_JOINED;
		if (thread_return) {
			*thread_return = all_threads[th]->ret_value;
		}
		if (all_threads[th]->join_to < 0) {
			/* th was a zombie because it had no sons and was waiting for a parent.
			 * now it has a parent, so we can finnally kill th.
			 */
			all_threads[th]->state=UTHREAD_DELETED;
			goto out_success;
		}
	}

	current->join_to = th;
	all_threads[th]->join_by = current->id;
	all_threads[th]->ret_value_joined = thread_return;
	deactivate_thread_and_cs(current);
	/* here returned from the join */
out_success:
	retval = UTHREAD_SUCCESS;

out_unlock:
	unlock_alarm();
	return retval;
}

/* yield the thread - calls signal SIGALRM */
void uthread_yield() {
	kill(getpid(),SIGALRM);
}

/* kill_all()
 * this method is called when thread 0 is either finished, exists or canceled.
 * frees all data structures before exiting the main program
 * output: none - we terminate the program.
 * note: this program is being called due to atexit(kill_all) call when we call uthread_init()
 */
void kill_all() {
	int i;
	for (i = 1; i< UTHREAD_MAX_THREADS; i++) {
		if (all_threads[i]) {
			all_threads[i]->state = UTHREAD_DELETED;
		}
	}
	garbage_collector();
	thread_list_destroy(all_threads[0]->locked_mutexes);
	uthread_mutex_free_general();
	free(all_threads[0]);
}

/* do_exit(thread,retval)
 * The method is called whenever a thread is cancelled, exists or finishes.
 * Wakes any joining threads, and marks any zombie threads that need to finish for deletion
 * Unlocks all mutexes that were locked by thread
 * input:
 * thread - the thread we wish to terminate
 * retval - the return value of the terminating thread
 *
 */
void do_exit(uthread thread, int retval) {
	if (thread->id == 0) {
		exit(retval);
	}
	thread->state = UTHREAD_ZOMBIE;
	thread->ret_value = retval;
	uthread_free_mutexes(thread);
	if (thread->join_by > -1) {
		thread->state = UTHREAD_ZOMBIE_JOINED; // thread has join_by and therefore must be UTHREAD_ZOMBIE_JOINED or UTHREAD_DELETED
		COND_ASSERT(all_threads[thread->join_by]);
		COND_ASSERT(all_threads[thread->join_by]->state != UTHREAD_RUNNING);
		if (thread->join_to < 0) {
			if (all_threads[thread->join_by]->state == UTHREAD_ZOMBIE_JOINED) {
				int idx = thread->join_by;
				while (all_threads[idx]->join_by > -1 && all_threads[idx]->state == UTHREAD_ZOMBIE_JOINED) {
					all_threads[idx]->state = UTHREAD_DELETED;
					idx = all_threads[idx]->join_by;
				}
				if (all_threads[idx]->state == UTHREAD_ZOMBIE_JOINED) {
					all_threads[idx]->state = UTHREAD_DELETED;
				}
				else if (all_threads[idx]->state == UTHREAD_SUSPENDED) {
					activate_thread(all_threads[idx]);
				}

				all_threads[idx]->join_to = -1;
			}
			else if (all_threads[thread->join_by]->state == UTHREAD_SUSPENDED) {
				activate_thread(all_threads[thread->join_by]);
			}
		}

		if (thread->ret_value_joined) {
			*(thread->ret_value_joined) = retval;
		}
		if (thread->join_to < 0) {
			all_threads[thread->join_by]->join_to = -1;
			thread->state = UTHREAD_DELETED;
			thread->join_by = -1;
		}
	}
}

/* lock_alarm()
 * freezes the ularam, for critical code that requires no context switch
 * stores the current time remaining in the current thread struct
 */
void lock_alarm() {
	current->lock_alarm = ualarm(0,0);
	if (current->lock_alarm == 0) {
		current->lock_alarm = 1;
	}
}
/* restores the ualarm with the previous remaining time */
void unlock_alarm() {
	ualarm(current->lock_alarm,0);
}

/* get_new_id()
 * goes over the global array of threads and finds the first unused array
 * output:
 * UTHREAD_FAIL - array is full
 * else - returns first unused ID
 */
int get_new_id() {
	int i;
	for (i = 0; i<UTHREAD_MAX_THREADS; i++) {
		if (!all_threads[i]) {
			break;
		}
	}
	return i == UTHREAD_MAX_THREADS ? UTHREAD_FAIL : i;
}

/* context_switch(prev,next)
 * calls stores current status for prev using sigsetjmp
 * switch to next using siglongjmp
 * calls garbage_collector afterwards to free any marked-for-deletion threads
 * return: 0, always. my context switch is hard-core and works all the time
 */
int context_switch(uthread prev, uthread next) {
	if (prev == next) {
		current = next; /* for safety if for some reason current is not prev */
		goto out;
	}
	if (sigsetjmp(current->current_instruction,1) == 0) {
		/* First time called, need to jump to the next.*/
		current = next;
		siglongjmp(current->current_instruction,68);
	}
	else {
		/* Welcome back! We missed you :D */
	}
out:
	garbage_collector();
	reset_alarm();
	return 0;
}

/* get_next_running(prev)
 * finds the first thread with ID higher then prev's ID, with RUNNING in its state
 * if no such thread is found, start from 0
 * input:
 * prev - thread you want to find its next thread
 *
 * output:
 * NULL - if for some reason we can't find the next running thread
 * else, thread - the next thread to run
 */
uthread get_next_running(uthread prev) {

	uthread next = NULL;
	uthread_id idx = (prev->id + 1) % UTHREAD_MAX_THREADS;
	if (prev->state == UTHREAD_RUNNING) {
		next = prev;
	}
	while (idx != prev->id) {
		if (all_threads[idx] && all_threads[idx]->state == UTHREAD_RUNNING) {
			next = all_threads[idx];
			break;
		}
		idx = (idx + 1) % UTHREAD_MAX_THREADS;
	}
	return next;
}

/* sig_handler(signum)
 * a handler for SIGALRM
 * swithches between the running thread and it's next on the running queue
 */
void sig_handler(int signum) {
	uthread prev,next;

	prev = current;
	next = get_next_running(current);

	COND_ASSERT(next);
	COND_ASSERT(next == all_threads[next->id]);
	context_switch(prev,next);

	return;
}

/* reset_alarm()
 * resets the alarm based on the prio of the current running thread
 */
void reset_alarm() {
	COND_ASSERT(UTHREAD_TIME_SLICE * current->prio > 0);
	ualarm(UTHREAD_TIME_SLICE * current->prio,0);
}

void activate_thread(uthread thread) {
	thread->state = UTHREAD_RUNNING;
}

void deactivate_thread(uthread thread) {
	thread->state = UTHREAD_SUSPENDED;
}

/* deactivates a given thread, and call context_switch.
 * we do this only if thread is current
 */
void deactivate_thread_and_cs(uthread thread) {
	COND_ASSERT(thread);
	deactivate_thread(thread);
	find_next_and_cs(thread);
}

/* finds the next running thread from given thread and context switches to it */
void find_next_and_cs(uthread thread) {
	uthread next = get_next_running(thread);
	while (!next) {
		sched_yield(); /* deadlock! */
		COND_ASSERT(thread);
		next = get_next_running(thread);
	}
	context_switch(thread,next);
}

/* garbage_collector()
 * called after each context_switch and before each thread_create attempt
 * goes over the global threads array all_threads and deletes each thread marked with DELETED status
 */
void garbage_collector() {
	uthread_id i;
	int ret;
	for (i = 1 ; i < UTHREAD_MAX_THREADS; i++) {
		if (all_threads[i] && all_threads[i]->state == UTHREAD_DELETED) {
			COND_ASSERT(i != 0);
			free(all_threads[i]->stack);
			thread_list_destroy(all_threads[i]->locked_mutexes);
			free(all_threads[i]);
			all_threads[i] = NULL;
		}
	}
}
